﻿
P12343[蓝桥杯 2025 省 AB / Python B 第二场] 树上寻宝


题目描述
小蓝正在一棵含有 n 个结点的树的根结点 1 上，他准备在这棵树上寻宝。结点 i 上有一个物品，价值为 w
i。然而，小蓝每次寻宝只能从根节点出发走不超过 k 步，每步只能选择走 1 条边或者 2 条边，
之后会自动拾取最终停留的结点上的物品并被传送回根结点。请求出小蓝最终能获得的物品的总价值。

输入格式
输入的第一行包含两个正整数 n, k，用一个空格分隔。

第二行包含 n 个正整数 w
1
​
, w
2
​
, ⋯, w
n
​
，相邻整数之间使用一个空格分隔。

接下来 n−1 行，每行包含两个正整数 u
i
​
, v
i
​
，用一个空格分隔，表示结点 u
i
​
和结点 v
i
​
之间有一条边。

输出格式
输出一行包含一个整数表示答案。

输入输出样例
输入 #1复制
8 2
6 3 3 1 5 4 3 4
1 2
2 3
2 4
4 5
5 6
6 7
7 8
输出 #1复制
22
说明 / 提示
样例说明
走 0 步能到的结点：1；
走 1 步能到的结点：2, 3, 4；
走 2 步能到的结点：3, 4, 5, 6；
因此能到的结点为：1, 2, 3, 4, 5, 6，能获得的总价值为 22。






















#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;//存放点与对应层数 
const int  N = 1e5 + 5;
bool vis[N];
int n, k; //点数，步数 
vector<int> w;//每个点的价值
vector<vector<int>>V;//V[i][j]表示i指向的点 
ll ans = 0;
int level[N];//dfs记录每一个点所在的层数 

//思路： 有题目可知，只要是点所在的层数小于等于2*k层即可到达，先搜索之后符合要求就统计，勿忘longlong 


//宽搜直接确定点只要符合层数要求就进行统计w和 
void  bfs_solve() {
    cin >> n >> k;
    w.resize(n + 1);//每个点的价值
    V.resize(n + 1);//V[i][j]表示i指向的点 
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        V[u].push_back(v);//默认双向边 
        V[v].push_back(u);
    }
    //层序遍历： 放入队列一定是层数合理就统计对应的w和 
    queue<PII> q;
    q.push({ 1,0 });
    vis[1] = 1;
    ans += w[1];
    while (!q.empty()) {
        int u = q.front().first;
        int level = q.front().second;
        q.pop();
        //把与之相连的点判断合法后放进去：
        for (int i = 0; i < V[u].size(); i++) {

            if (level + 1 <= 2 * k && !vis[V[u][i]]) { //双向边防止重复采用vis数组 
                q.push({ V[u][i],level + 1 });
                vis[V[u][i]] = 1;
                ans += w[V[u][i]];

            }
        }

    }
    cout << ans << endl;
}


void  sub_dfs(int cur, int last) {//cur为当前点，last为上一个点，防止双向边重复判断 

    for (int i = 0; i < V[cur].size(); i++) {
        if (V[cur][i] != last) {
            level[V[cur][i]] = level[cur] + 1;//填充cur连接的下一个节点的层数 
            sub_dfs(V[cur][i], cur);
        }
    }

}

//先广搜确定好每个点的层数，在统计： 
void dfs_solve() {
    cin >> n >> k;
    w.resize(n + 1);//每个点的价值
    V.resize(n + 1);//V[i][j]表示i指向的点  
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        V[u].push_back(v);
        V[v].push_back(u);
    }

    sub_dfs(1, 0);//完成每个节点对应的level统计 

    for (int i = 1; i <= n; i++) {
        if (level[i] <= 2 * k) ans += w[i];
    }
    cout << ans << endl;


}
int main() {
    //bfs_solve();
    dfs_solve();
    return 0;
}